/*
 * @Author: liusheng
 * @Date: 2022-04-10 17:23:36
 * @LastEditors: liusheng
 * @LastEditTime: 2022-06-19 09:30:57
 * @Description: 
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 
 剑指 Offer II 020. 回文子字符串的个数
给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

 

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
 

提示：

1 <= s.length <= 1000
s 由小写英文字母组成
 

注意：本题与主站 647 题相同：https://leetcode-cn.com/problems/palindromic-substrings/ 

假设 n = 4，我们可以把可能的回文中心列出来：

编号 i	回文中心左起始位置 l_i  回文中心右起始位置 r_i
i
​
 
0	0	0
1	0	1
2	1	1
3	1	2
4	2	2
5	2	3
6	3	3
由此我们可以看出长度为 nn 的字符串会生成 2n−1 组回文中心 [l_i, r_i]
 */
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        
        int count = 0;
        //palindrome center solution
        //n element has 2 * n - 1 center(left,right pair)
        for (int i = 0; i <  2 * n - 1; ++i)
        {
            //palindrome center left
            int left = i / 2;
            //palindrome center right
            int right = i / 2 + i % 2;
            while (left >= 0 && right < n && s[left] == s[right])
            {
                --left;
                ++right;
                ++count;
            }
        }

        return count;
    }
};

class Solution2 {
public:
    int countSubstrings(string s) {
        int n = s.size();
        int count = 0;
        //Palindromic center solution
        for (int i = 0; i < n; ++i)
        {
            //center i , i
            count += countSubstrings(s,i,i);
            //center i , i + 1
            count += countSubstrings(s,i,i+1);
        }
        
        return count;
    }
private:
    int countSubstrings(string & s, int left,int right)
    {
        int n = s.size();
        int count = 0;
        while (left >= 0 && right < n && s[left--] == s[right++])
        {
            ++count;
        }
        return count;
    }
};

/*
Advancement:
use Manacher's algorithm
not figure out,leave for next time
*/

class Solution3 {
public:
    int countSubstrings(string s) {
        int n = s.size();
        string t = "$#";
        for (const char &c: s) {
            t += c;
            t += '#';
        }
        n = t.size();
        t += '!';

        auto f = vector <int> (n);
        int iMax = 0, rMax = 0, ans = 0;
        for (int i = 1; i < n; ++i) {
            // 初始化 f[i]
            f[i] = (i <= rMax) ? min(rMax - i + 1, f[2 * iMax - i]) : 1;
            // 中心拓展
            while (t[i + f[i]] == t[i - f[i]]) ++f[i];
            // 动态维护 iMax 和 rMax
            if (i + f[i] - 1 > rMax) {
                iMax = i;
                rMax = i + f[i] - 1;
            }
            // 统计答案, 当前贡献为 (f[i] - 1) / 2 上取整
            ans += (f[i] / 2);
        }

        return ans;
    }
};
